﻿//2021年11月6日，英雄联盟全球总决赛打响，中国电子竞技战队Edward Gaming（EDG）以3 : 2力克韩国强敌DWG KIA（DK）战队，历史上首次夺得全球总冠军。一时间全网沸腾，大家纷纷在社交平台上直呼“edgnb”。现给定一段文本，请编写程序识别出连续的k个“edgnb”组成的字符串在该文本中出现了多少次。
//
//输入格式 :
//第一行为1个整数T，表示数据组数。对于每组数据，第一行为1个字符串，表示给定的文本。第二行为1个整数k，含义如题目所述。（1≤T≤10。各组数据给定的字符串长度之和不超过10
//5
//，且字符串中只包含a - z的小写字母。k≥1且k×5小于给定字符串长度）。
//
//输出格式 :
//对于每组数据输出一行，为1个整数，表示所求的出现次数。
#include <stdio.h>
#include <string.h>

#define MAX 100000

// 生成由k个"edgnb"组成的目标字符串
void generate_target(char* target, int k) {
    const char* pattern = "edgnb";
    target[0] = '\0'; // 清空目标字符串
    for (int i = 0; i < k; i++) {
        strcat(target, pattern);
    }
}

int main() {
    int T;
    scanf("%d", &T); // 读取数据组数

    while (T--) {
        char text[MAX + 1];
        int k;

        scanf("%s", text);
        scanf("%d", &k);

        int textLen = strlen(text);
        int targetLen = 5 * k; // 目标字符串的长度是"edgnb"的长度乘以k

        // 如果文本长度小于目标字符串的长度，直接输出0
        if (textLen < targetLen) {
            printf("0\n");
            continue;
        }

        // 生成由k个"edgnb"组成的目标字符串
        char target[targetLen + 1];
        generate_target(target, k);

        // 滑动窗口法查找目标字符串在文本中的出现次数
        int count = 0;
        for (int i = 0; i <= textLen - targetLen; i++) {
            if (strncmp(&text[i], target, targetLen) == 0) {
                count++;
            }
        }

        // 输出结果
        printf("%d\n", count);
    }

    return 0;
}
